import java.util.HashSet;
import java.util.Set;

/*
 * @lc app=leetcode.cn id=41 lang=java
 *
 * [41] 缺失的第一个正数
 */

// @lc code=start
class Solution {
    /**
    * Accepted
    173/173 cases passed (1 ms)
    Your runtime beats 97.26 % of java submissions
    Your memory usage beats 80.34 % of java submissions (49.5 MB)
    */
    public int firstMissingPositive(int[] nums) {
        int temp = 1, len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] == 1) {
                temp = 0;
            } else if (nums[i] < 1 || nums[i] > len) {
                nums[i] = 1;
            }
        }
        if (temp == 1)
            return 1;
        for (int i = 0; i < len; i++) {
            temp = Math.abs(nums[i]) - 1;
            if (nums[temp] > 0) {
                nums[temp] = -nums[temp];
            }
        }
        for (int i = 1; i < len; i++) {
            if (nums[i] > 0)
                return i + 1;
        }
        return len + 1;
    }

    /**
     * Accepted
    173/173 cases passed (9 ms)
    Your runtime beats 10.2 % of java submissions
    Your memory usage beats 72.74 % of java submissions (49.7 MB)
     */
    public int firstMissingPositive0(int[] nums) {
        Set set = new HashSet<Integer>();
        int len = nums.length;
        for (int val : nums) {
            if (val > 0 && val <= len) {
                set.add(val);
            }
        }
        for (int i = 1; i <= len; i++) {
            if (!set.contains(i))
                return i;
        }
        return len + 1;
    }
}
// @lc code=end
